#ifdef a
#include"BinaryTree.h"
#include"Quene-tree.h"
//节点创建
BTNode* BuyBTNode(BTTYPE val) {
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (!newnode) {
		assert(0);
		return NULL;
	}
	newnode->val = val;
	newnode->right = NULL;
	newnode->left = NULL;
	return newnode;
}

//二叉树初始化
//BTNode* BTTreeCreat() {
	//BTNode* node1 = BuyBTNode(1);
	//BTNode* node2 = BuyBTNode(2);
	//BTNode* node3 = BuyBTNode(3);
	//BTNode* node4 = BuyBTNode(4);
	//BTNode* node5 = BuyBTNode(5);
	//BTNode* node6 = BuyBTNode(6);

	//node1->left = node2;
	//node1->right = node4;
	//node2->left = node3;
	//node4->left = node5;
	//node4->right = node6;

	//return node1;
//}

//二叉树初始化(NULL标记为-1)
BTNode* BTTreeCreat(int* array,int size, BTTYPE flag, int* index) {
	BTNode* root = NULL;
	if ((*index) < size && array[*index] != flag) {
		root = BuyBTNode(array[*index]);
		(*index)++;
		root->left = BTTreeCreat(array, size, flag, index);
		(*index)++;
		root->right = BTTreeCreat(array, size, flag, index);
	}
	return root;
}

BTNode* BTTreeInit(int* array, int size, BTTYPE flag) {
	int index = 0;
	return BTTreeCreat(array, size, flag, &index);
}

//前序遍历(根左右)
void PreOrder(BTNode* root) {
	if (!root) {
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}


//中序遍历(左根右)
void InOrder(BTNode* root) {
	if (!root)
		return;
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
	return;
}

//后序遍历(左右根)
void PosOrder(BTNode* root) {
	if (!root)
		return;
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d ", root->val);
	return;
}

//层序遍历
void LevelOrder(BTNode* root) {
	//利用堆-》先进先出
	if (!root)
		return;
	Quene q;
	BTQueneInit(&q);
	BTQuenePush(&q, root);
	while (!BTQueneIsEmpty(&q)) {
		BTNode* cur = BTQueneFront(&q);
		BTQueneOut(&q);
		printf("%d ", cur->val);
		if(cur->left)
			BTQuenePush(&q, cur->left);
		if(cur->right)
			BTQuenePush(&q, cur->right);
	}
	BTQueneDestory(&q);
	return;
}

//二叉树第k层节点个数
int BinaryTreeLeverSize(BTNode* root, int k) {
	if (k <= 0 || !root)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLeverSize(root->left, k - 1) + BinaryTreeLeverSize(root->right, k - 1);
}	


//二叉树节点总个数
int BinaryTreeSize(BTNode* root) {
	if (!root)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) {
	if (!root)
		return 0;
	if (!root->left && !root->right)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

//二叉树的高度
int BinaryTreeHeight(BTNode* root) {
	if (!root)
		return 0;
	//return BinaryTreeHeight(root->left) + 1 > BinaryTreeHeight(root->right) + 1? BinaryTreeHeight(root->left) + 1 : BinaryTreeHeight(root->right) + 1;
	return 1 + (BinaryTreeHeight(root->left) > BinaryTreeHeight(root->right)? BinaryTreeHeight(root->left): BinaryTreeHeight(root->right));
}

//二叉树中的查找
BTNode* BinartTreeFind(BTNode* root, BTTYPE val) {
	BTNode* ret = NULL;
	if (!root)
		return NULL;
	if (root->val == val)
		return root;
//	if (BinartTreeFind(root->left, val))
//		return BinartTreeFind(root->left, val);
	if (ret = BinartTreeFind(root->left, val))
		return ret;
	return BinartTreeFind(root->right, val);
}

//判断是否为完全二叉树
int BinaryTreeComplete(BTNode* root) {
	int flag = 0;//不饱和点标记
	Quene q;
	BTQueneInit(&q);
	BTQuenePush(&q, root);
	while (!BTQueneIsEmpty(&q)) {
		BTNode* cur = BTQueneFront(&q);
		BTQueneOut(&q);
		if (flag) {
			if (cur->left || cur->right)
				return 0;
		}
		else {
			if (cur->left && cur->right) {
				BTQuenePush(&q, cur->left);
				BTQuenePush(&q, cur->left);
			}
			else if (cur->left) {
				BTQuenePush(&q, cur->left);
				flag = 1;
			}
			else if (cur->right) {
				return 0;
			}
			else {
				flag = 1;
			}

		}
	}
	BTQueneDestory(&q);
	return 1;
}

//二叉树的销毁
void BinaryTreeDestory(BTNode** root) {
	if (!(*root))
		return;
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

//---------------------------------------------------------------------------

//测试
void TestBT() {
	//int array[] = { 1,2,3 ,-1,-1,-1,4,5,-1,-1,6,-1,-1 };//根左右
	int array[] = { 1,2,3 ,-1,-1, 1, -1, -1,4,5,-1,-1,6,-1,-1 };//根左右
	BTNode* root = BTTreeInit(array, sizeof(array) / sizeof(array[0]), -1);
	PreOrder(root);	
	printf("\n");
	InOrder(root);
	printf("\n");
	PosOrder(root);
	printf("\n");
	LevelOrder(root);
	printf("\n");
	printf("BTTree size = %d\n", BinaryTreeSize(root));
	int i = 6;
	while (i--)
		printf("BTTree lever( %d ) size = %d\n", i, BinaryTreeLeverSize(root, i));
	
	printf("BTTree leaf size = %d\n", BinaryTreeLeafSize(root));
	printf("BTTree height = %d\n", BinaryTreeHeight(root));
	BTNode* ret = NULL;
	if (ret = BinartTreeFind(root, 5))
		printf("%d 存在\n", ret->val);
	else
		printf("不存在!\n");

	if (BinaryTreeComplete(root)) {
		printf("是完全二叉树!\n");
	}
	else
		printf("不是完全二叉树!\n");
	BinaryTreeDestory(&root);
	return;
}

#endif 